{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #DI String Match"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diStringMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #增减字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>由范围 <code>[0,n]</code> 内所有整数组成的 <code>n + 1</code> 个整数的排列序列可以表示为长度为 <code>n</code> 的字符串 <code>s</code> ，其中:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>perm[i] &lt; perm[i + 1]</code>&nbsp;，那么&nbsp;<code>s[i] == 'I'</code>&nbsp;</li>\n",
    "\t<li>如果&nbsp;<code>perm[i] &gt; perm[i + 1]</code>&nbsp;，那么 <code>s[i] == 'D'</code>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个字符串 <code>s</code> ，重构排列&nbsp;<code>perm</code> 并返回它。如果有多个有效排列perm，则返回其中 <strong>任何一个</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"IDID\"\n",
    "<strong>输出：</strong>[0,4,1,3,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"III\"\n",
    "<strong>输出：</strong>[0,1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"DDI\"\n",
    "<strong>输出：</strong>[3,2,0,1]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code><font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">s</span></span></font></font></code> 只包含字符&nbsp;<code>\"I\"</code>&nbsp;或&nbsp;<code>\"D\"</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [di-string-match](https://leetcode.cn/problems/di-string-match/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [di-string-match](https://leetcode.cn/problems/di-string-match/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"IDID\"', '\"III\"', '\"DDI\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        min_ = 0\n",
    "        max_ = len(s)\n",
    "\n",
    "        res = []\n",
    "        for ch in s:\n",
    "            if ch == 'I':\n",
    "                res.append(min_)\n",
    "                min_ += 1\n",
    "            else:\n",
    "                res.append(max_)\n",
    "                max_ -= 1\n",
    "        res.append(max_)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef diStringMatch(self, s: str) -> List[int]:\n",
    "\t\tstart = s.count('D')\n",
    "\t\tresult = [start]\n",
    "\t\tup_num, down_num = 1, 1\n",
    "\t\tfor ch in s:\n",
    "\t\t\tif ch == 'I':\n",
    "\t\t\t\tresult.append(start + up_num)\n",
    "\t\t\t\tup_num += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tresult.append(start - down_num)\n",
    "\t\t\t\tdown_num += 1\n",
    "\t\treturn result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            res[i] = res[i-1]+ (1 if s[i-1] == 'I' else -1)\n",
    "        idx = list(range(n+1))\n",
    "        idx.sort(key = lambda i: res[i])\n",
    "        res = [0]*(n+1)\n",
    "        for i in range(n+1):\n",
    "            res[idx[i]] = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        lst1=[x for x in s]\n",
    "        lst2=[x for x in range(0,len(lst1)+1)]\n",
    "        lst4=[x for x in range(0,len(lst1)+1)]\n",
    "        lst3=[]\n",
    "        a=0\n",
    "        b=-1\n",
    "        for x in lst1:\n",
    "            if x=='I':\n",
    "                lst3.append(lst2[a])\n",
    "                lst4.remove(lst2[a])\n",
    "                a+=1\n",
    "            if x=='D':\n",
    "                lst3.append(lst2[b])\n",
    "                lst4.remove(lst2[b])\n",
    "                b-=1\n",
    "        lst3.append(lst4[0])\n",
    "        return lst3\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left = 0\n",
    "        right = n = len(s)\n",
    "        perm = [0] * (n + 1)\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'I':\n",
    "                perm[i] = left\n",
    "                left += 1\n",
    "            else:\n",
    "                perm[i] = right\n",
    "                right -= 1\n",
    "        perm[n] = left  # 最后剩下一个数，此时 lo == hi\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans = []\n",
    "        l = 0\n",
    "        r = len(s) \n",
    "        for each in s:\n",
    "            if each == 'I':\n",
    "                ans.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                ans.append(r)\n",
    "                r -= 1\n",
    "        ans.append(l)\n",
    "        return ans\n",
    "        # ans = []\n",
    "        # n = len(s)\n",
    "        # queue = collections.deque()\n",
    "        # for i in range(n+1):\n",
    "        #     queue.append(i)\n",
    "        # for each in s:\n",
    "        #     if each == 'I':\n",
    "        #         ans.append(queue.popleft())\n",
    "        #     else: \n",
    "        #         ans.append(queue.pop())\n",
    "        # ans.append(queue.popleft())\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s) \n",
    "        rest = set(range(n+1))\n",
    "        perm = []\n",
    "        for i in range(n):\n",
    "            if s[i] == 'I':\n",
    "                min_val = min(rest)\n",
    "                perm.append(min_val)\n",
    "                rest.remove(min_val)\n",
    "            else:\n",
    "                max_val = max(rest)\n",
    "                perm.append(max_val)\n",
    "                rest.remove(max_val)\n",
    "        perm.append(list(rest)[0])\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans, o = list(), s.count(\"I\")\n",
    "        small, large = 0, len(s)\n",
    "        for x in s:\n",
    "            if x == \"D\":\n",
    "                ans.append(large)\n",
    "                large -= 1\n",
    "            else:\n",
    "                ans.append(small)\n",
    "                small += 1\n",
    "        ans.append(small)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        lo = 0\n",
    "        hi = n = len(s)\n",
    "        perm = [0]*(n+1)\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch == 'I':\n",
    "                perm[i] = lo\n",
    "                lo += 1\n",
    "            else:\n",
    "                perm[i] = hi\n",
    "                hi -= 1\n",
    "        perm[n] = lo\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        lower = 0\n",
    "        heigh = len(s)\n",
    "        res = [0]*(heigh+1)\n",
    "        for i,x in enumerate(s):\n",
    "            if x == \"I\":\n",
    "                res[i]=lower\n",
    "                lower+=1\n",
    "            elif x ==\"D\":\n",
    "                res[i]=heigh\n",
    "                heigh-=1\n",
    "        res[-1]=heigh\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        i, j = 0, len(s)\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            if c == \"I\":\n",
    "                ans.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(j)\n",
    "                j -= 1\n",
    "        ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l, r = 0, len(s)\n",
    "        res = []\n",
    "        for i in s:\n",
    "            if i == \"I\":\n",
    "                res.append(l)\n",
    "                l +=1\n",
    "            else:\n",
    "                res.append(r)\n",
    "                r -= 1\n",
    "        res.append(l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        r = len(s)\n",
    "        l = 0\n",
    "        ans = [0] * (r + 1)\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'I':\n",
    "                ans[i] = l\n",
    "                l += 1\n",
    "            else:\n",
    "                ans[i] = r\n",
    "                r -= 1\n",
    "        ans[-1] = l\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left, right, res = 0, len(s), []\n",
    "        for item in s:\n",
    "            if item=='I':\n",
    "                res.append(left)\n",
    "                left += 1\n",
    "            else:\n",
    "                res.append(right)\n",
    "                right -= 1\n",
    "        res.append(left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        i = 0\n",
    "        d = len(s)\n",
    "        res = []\n",
    "        for j in s:\n",
    "            if j == 'I':\n",
    "                res.append(i)\n",
    "                i = i + 1\n",
    "            elif j == 'D':\n",
    "                res.append(d)\n",
    "                d = d-1\n",
    "        if s[-1] == 'D':\n",
    "            res.append(res[-1]-1)\n",
    "        else:\n",
    "            res.append(res[-1]+1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        res = []\n",
    "        i,j = 0,len(s)\n",
    "        for ch in s:\n",
    "            if ch == 'I':\n",
    "                res.append(i)\n",
    "                i += 1\n",
    "            elif ch == 'D':\n",
    "                res.append(j)\n",
    "                j -= 1\n",
    "        res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)\n",
    "        a=list(range(l+1))\n",
    "        lb=0\n",
    "        ub=l\n",
    "        for i in range(l):\n",
    "            if s[i]=='I':\n",
    "                a[i]=lb\n",
    "                lb=lb+1\n",
    "            else:\n",
    "                a[i]=ub\n",
    "                ub=ub-1\n",
    "        a[l]=lb\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> list[int]:\n",
    "        n = len(s)\n",
    "        arr = [i for i in range(n + 1)]\n",
    "        ans = []\n",
    "        for ch in s:\n",
    "            if ch == 'I':\n",
    "                ans.append(arr.pop(0))\n",
    "            else:\n",
    "                ans.append(arr.pop())\n",
    "        ans.append(arr[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        left,right,ans=0,n,[]\n",
    "        for i in s:\n",
    "            if i=='I':\n",
    "                ans.append(left)\n",
    "                left+=1\n",
    "            else:\n",
    "                ans.append(right)\n",
    "                right-=1\n",
    "        ans.append(left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left, right, ans = 0, len(s), []\n",
    "        for c in s:\n",
    "            if c == 'I':\n",
    "                ans.append(left)\n",
    "                left += 1\n",
    "            else:\n",
    "                ans.append(right)\n",
    "                right -= 1\n",
    "        ans.append(left)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)\n",
    "        res=[]\n",
    "        tmin=0\n",
    "        tmax=l\n",
    "        for i in s:\n",
    "            if i==\"I\":\n",
    "                res.append(tmin)\n",
    "                tmin+=1\n",
    "            else:\n",
    "                res.append(tmax)\n",
    "                tmax-=1\n",
    "        res.append(tmax)\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        #复杂化\n",
    "        '''from queue import PriorityQueue\n",
    "        res,used,n=[],set(),len(s)\n",
    "        mini,maxi=PriorityQueue(),PriorityQueue()\n",
    "        for i in range(n+1):\n",
    "            mini.put(i)\n",
    "            maxi.put(-i)\n",
    "        for i in range(n):\n",
    "            if s[i]=='I':\n",
    "                while mini:\n",
    "                    d=mini.get()\n",
    "                    if d not in used:\n",
    "                        res.append(d)\n",
    "                        used.add(d)\n",
    "                        break\n",
    "            else:\n",
    "                while maxi:\n",
    "                    d=maxi.get()\n",
    "                    if d not in used:\n",
    "                        res.append(-d)\n",
    "                        used.add(-d)\n",
    "                        break\n",
    "        if mini.qsize==1:\n",
    "            res.append(mini.get())\n",
    "        else:\n",
    "            res.append(-maxi.get())\n",
    "        return res'''\n",
    "        '''res,n=[],len(s)\n",
    "        digits=[i for i in range(n+1)]\n",
    "        l,r=0,n\n",
    "        for i in range(n):\n",
    "            if s[i]=='I':\n",
    "                res.append(digits[l])\n",
    "                l+=1\n",
    "            else:\n",
    "                res.append(digits[r])\n",
    "                r-=1\n",
    "        res.append(digits[l])\n",
    "        return res'''\n",
    "        ret,n=[],len(s)\n",
    "        l,r=0,n\n",
    "        for i in range(n):\n",
    "            if s[i]=='I':\n",
    "                ret.append(l)\n",
    "                l+=1\n",
    "            else:\n",
    "                ret.append(r)\n",
    "                r-=1\n",
    "        ret.append(l)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        l = 0\n",
    "        r = n\n",
    "        ans = []\n",
    "        for x in s:\n",
    "            if x == 'I':\n",
    "                ans.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                ans.append(r)\n",
    "                r -= 1\n",
    "        ans.append(l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        lo = 0\n",
    "        hi = n = len(s)\n",
    "        ans = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            if s[i]=='I':\n",
    "                ans[i]=lo \n",
    "                lo+=1\n",
    "            else:\n",
    "                ans[i]=hi \n",
    "                hi-=1\n",
    "        ans[n]=lo \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left,right,ans=0,len(s),[]\n",
    "        for c in s:\n",
    "            if c=='I':\n",
    "                ans.append(left)\n",
    "                left+=1\n",
    "            else:\n",
    "                ans.append(right)\n",
    "                right-=1\n",
    "        ans.append(left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        l=0\n",
    "        r=n\n",
    "        perm=[0]*(n+1)\n",
    "        for i,ss in enumerate(s):\n",
    "            if ss=='I':\n",
    "                perm[i]=l\n",
    "                l+=1\n",
    "            else:\n",
    "                perm[i]=r\n",
    "                r-=1\n",
    "        perm[-1]=l\n",
    "        return perm\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)\n",
    "        a=list(range(l+1))\n",
    "        lb=0\n",
    "        ub=l\n",
    "        for i in range(l):\n",
    "            if s[i]=='I':\n",
    "                a[i]=lb\n",
    "                lb=lb+1\n",
    "            else:\n",
    "                a[i]=ub\n",
    "                ub=ub-1\n",
    "        a[l]=lb\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        # s中的I和D：I 升序，D 倒序\n",
    "        n=len(s)\n",
    "        perm=[k for k in range(n+1)]  \n",
    "        for _ in range(n+1):\n",
    "            flag=False\n",
    "            i,j=0,0\n",
    "            while i<n:\n",
    "                if s[i]==\"I\" and perm[j]>perm[j+1]:  # 此时应该判断对应位置的perm两个数是否升序\n",
    "                    perm[j],perm[j+1]=perm[j+1],perm[j]\n",
    "                    flag=True\n",
    "                elif s[i]==\"D\" and perm[j]<perm[j+1]:\n",
    "                    perm[j],perm[j+1]=perm[j+1],perm[j]  # 前后交换\n",
    "                    flag=True\n",
    "                j+=1\n",
    "                i+=1\n",
    "            if flag==False:\n",
    "                break\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def diStringMatch(self, s: str) -> List[int]:\r\n",
    "        n = len(s)\r\n",
    "        ans = list(range(n+1))\r\n",
    "        i = 0\r\n",
    "        while i < n:\r\n",
    "            j = i\r\n",
    "            while j < n and s[j] == 'D':\r\n",
    "                j += 1\r\n",
    "            if j > i:\r\n",
    "                ans[i:j+1] = reversed(ans[i:j+1])\r\n",
    "                i = j\r\n",
    "            i += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l, r = 0, len(s)\n",
    "        res = []\n",
    "        for i in s:\n",
    "            if i == \"I\":\n",
    "                res.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                res.append(r)\n",
    "                r -= 1\n",
    "        res.append(l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        # s中的I和D：I 升序，D 倒序\n",
    "        n=len(s)\n",
    "        perm=[k for k in range(n+1)]  \n",
    "        for _ in range(n+1):\n",
    "            flag=False  # 不加 超时\n",
    "            i,j=0,0\n",
    "            while i<n:\n",
    "                if s[i]==\"I\" and perm[j]>perm[j+1]:  # 此时应该判断对应位置的perm两个数是否升序\n",
    "                    perm[j],perm[j+1]=perm[j+1],perm[j]    # 前后交换\n",
    "                    flag=True\n",
    "                elif s[i]==\"D\" and perm[j]<perm[j+1]:\n",
    "                    perm[j],perm[j+1]=perm[j+1],perm[j]  \n",
    "                    flag=True\n",
    "                j+=1\n",
    "                i+=1\n",
    "            if flag==False:\n",
    "                break\n",
    "        return perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        allnum = []\n",
    "        for i in range(len(s)+1):\n",
    "            allnum.append(i)\n",
    "        output=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'I':\n",
    "                output.append(min(allnum))\n",
    "                allnum.remove(min(allnum))\n",
    "            if s[i] == 'D':\n",
    "                output.append(max(allnum))\n",
    "                allnum.remove(max(allnum))\n",
    "        output.append(max(allnum))\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        a=[]\n",
    "        b=0\n",
    "        c=len(s)\n",
    "        for i in s:\n",
    "            if i == 'I':\n",
    "                a.append(b)\n",
    "                b+=1\n",
    "            elif i==\"D\":\n",
    "                a.append(c)\n",
    "                c-=1\n",
    "        a.append(b)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left=0\n",
    "        right=n=len(s)\n",
    "        perm=[0]*(n+1)\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch=='I':\n",
    "                perm[i]=left\n",
    "                left+=1\n",
    "            else:\n",
    "                perm[i]=right\n",
    "                right-=1\n",
    "        perm[n]=left\n",
    "        return perm\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        l,r = 0,len(s)\n",
    "        res = []\n",
    "        for i in s:\n",
    "            if i == \"I\":\n",
    "                res.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                res.append(r)\n",
    "                r -= 1\n",
    "        if s[-1] == \"I\":\n",
    "            res.append(res[-1]+1)\n",
    "        else:\n",
    "            res.append(res[-1]-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        perm=[]\n",
    "        a=[i for i in range(len(s)+1)]\n",
    "        for i in s:\n",
    "            if i=='I':\n",
    "                perm.append(min(a))\n",
    "                a.remove(min(a))\n",
    "            else:\n",
    "                perm.append(max(a))\n",
    "                a.remove(max(a))\n",
    "        return perm+a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        l,r = 0,len(s)\n",
    "        res = []\n",
    "        for i in s:\n",
    "            if i == \"I\":\n",
    "                res.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                res.append(r)\n",
    "                r -= 1\n",
    "        res.append(l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left, right, ans = 0, len(s), []\n",
    "        for c in s:\n",
    "            if c == 'I':\n",
    "                ans.append(left)\n",
    "                left += 1\n",
    "            else:\n",
    "                ans.append(right)\n",
    "                right -= 1\n",
    "        ans.append(left)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        length=len(s)\n",
    "        i=0;d=length\n",
    "        answer=[]\n",
    "        for j in range(length):\n",
    "            if s[j]==\"I\":\n",
    "                answer.append(i)\n",
    "                i+=1\n",
    "            else:\n",
    "                answer.append(d)\n",
    "                d-=1\n",
    "        answer.append(i)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)\n",
    "        res=[]\n",
    "        tmin=0\n",
    "        tmax=l\n",
    "        for i in s:\n",
    "            if i==\"I\":\n",
    "                res.append(tmin)\n",
    "                tmin+=1\n",
    "            else:\n",
    "                res.append(tmax)\n",
    "                tmax-=1\n",
    "        res.append(tmin)\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        allnum = []\n",
    "        for i in range(len(s)+1):\n",
    "            allnum.append(i)\n",
    "        output=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'I':\n",
    "                output.append(min(allnum))\n",
    "                allnum.remove(min(allnum))\n",
    "            if s[i] == 'D':\n",
    "                output.append(max(allnum))\n",
    "                allnum.remove(max(allnum))\n",
    "        output.append(max(allnum))\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(s)\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            if c == 'I':\n",
    "                ans.append(left)\n",
    "                left += 1\n",
    "            else:\n",
    "                ans.append(right)\n",
    "                right -= 1\n",
    "        ans.append(left)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)+1\n",
    "        t=list(range(0,l))\n",
    "        res=[]\n",
    "        for i in s:\n",
    "            if i==\"I\":\n",
    "                res.append(t.pop(0))\n",
    "            elif i==\"D\":\n",
    "                res.append(t.pop(-1))\n",
    "        res.append(t[0])\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ret = []\n",
    "        n = len(s)\n",
    "        temp = [index for index in range(n+1)]\n",
    "        for item in s:\n",
    "            if item == 'I':\n",
    "                ret.append(temp.pop(temp.index(min(temp))))\n",
    "            else:\n",
    "                ret.append(temp.pop(temp.index(max(temp))))\n",
    "        ret.append(temp[0])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        s = 'I' + s\n",
    "        d_acc = []\n",
    "        d_cnt = 0\n",
    "        for ch in s[::-1]:\n",
    "            d_acc.append(d_cnt)\n",
    "            if ch == 'D':\n",
    "                d_cnt += 1\n",
    "            \n",
    "        d_acc = d_acc[::-1]\n",
    "        ans = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'I':\n",
    "                ans.append(i + d_acc[i])\n",
    "            else:\n",
    "                ans.append(d_acc[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        _max = len(s)\n",
    "        _min = 0\n",
    "        _res = []\n",
    "        if s[0] == \"I\":\n",
    "            _res.append(0)\n",
    "            _min += 1\n",
    "        else:\n",
    "            _res.append(_max)\n",
    "            _max -= 1\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i] == \"I\":\n",
    "                if s[i + 1] == \"D\":\n",
    "                    _res.append(_max)\n",
    "                    _max -= 1\n",
    "                else:\n",
    "                    _res.append(_min)\n",
    "                    _min += 1\n",
    "            else:\n",
    "                if s[i + 1] == \"D\":\n",
    "                    _res.append(_max)\n",
    "                    _max -= 1\n",
    "                else:\n",
    "                    _res.append(_min)\n",
    "                    _min += 1\n",
    "        _res.append(_min)\n",
    "        return _res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        a = list(range(len(s)+1))\n",
    "        p = 0\n",
    "        q = len(s)\n",
    "        result = []\n",
    "        for char in s:\n",
    "            if char == 'I':\n",
    "                result.append(a[p])\n",
    "                p+=1\n",
    "            if char == 'D':\n",
    "                result.append(a[q])\n",
    "                q=q-1\n",
    "        result.append(a[p])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [i for i in range(n+1)]\n",
    "        l = 0\n",
    "        j = n\n",
    "        res_1 = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == 'I':\n",
    "                res_1.append(res[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                res_1.append(res[j])\n",
    "                j -= 1\n",
    "            i += 1\n",
    "        res_1.append(res[l])\n",
    "        return res_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        # numi = s.count(\"I\")\n",
    "        # numd = s.count(\"D\")\n",
    "        st = [0]\n",
    "        for it in s:\n",
    "            if it == \"I\":\n",
    "                st.append(max(st)+1)\n",
    "            if it == \"D\":\n",
    "                st.append(min(st)-1)\n",
    "        st = [x-min(st) for x in st]\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans = []\n",
    "        i, l, r = 0, 0, len(s)\n",
    "        while i < len(s):\n",
    "            if s[i] == 'I':\n",
    "                ans.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                ans.append(r)\n",
    "                r -= 1\n",
    "            i += 1\n",
    "        ans.append(l)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def diStringMatch2(self, s: str) -> List[int]:\n",
    "        # 双指针\n",
    "        ans = []\n",
    "        l, r = 0, len(s)\n",
    "        for i, j in enumerate(s):\n",
    "            if j == 'I':\n",
    "                if i == 0:\n",
    "                    ans.append(l)\n",
    "                    l += 1\n",
    "                ans.append(l)\n",
    "                l += 1\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans.append(r)\n",
    "                    r -= 1\n",
    "                ans.append(r)\n",
    "                r -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def diStringMatch1(self, s: str) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(s)\n",
    "        ans = [0 for i in range(right+1)]\n",
    "        for i in range(right):\n",
    "            if s[i] == 'I':\n",
    "                ans[i] = left\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[i] = right\n",
    "                right -= 1\n",
    "        ans[len(s)] = left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        #l算法步骤： 1.构造目标数组时，我们假设目标数组第一个数字是0; \n",
    "        targets = [0]\n",
    "        #2.初始化最大值为0，最小值为0，开始遍历字符串s; \n",
    "        min_p, max_p = 0, 0\n",
    "        for ss in s:\n",
    "            #3.遇到 'I'，最大值+1，最大值加入目标数组; \n",
    "            if ss == 'I':\n",
    "                max_p +=1\n",
    "                targets.append(max_p)\n",
    "            #4.遇到'D'，最小值-1，最小值加入目标数组;\n",
    "            else:\n",
    "                min_p -= 1\n",
    "                targets.append(min_p)\n",
    "        # 5.最后将目标数组中的所有值上移-min个单位;\n",
    "        return [i-min_p for i in targets]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n, stack = len(s), collections.deque()\n",
    "        cnts = [0 for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            if s[i] == 'I': cnts[i] += 1\n",
    "            else: cnts[i + 1] += 1\n",
    "        for i, cnt in enumerate(cnts):\n",
    "            if cnt == 0: stack.append(i)\n",
    "        ans, val = [-1 for _ in range(n + 1)], n\n",
    "        while stack:\n",
    "            i = stack.popleft()\n",
    "            ans[i] = val\n",
    "            val -= 1\n",
    "            if i > 0 and s[i - 1] == 'I':\n",
    "                cnts[i - 1] -= 1\n",
    "                if cnts[i - 1] == 0: stack.append(i - 1)\n",
    "            if i < n and s[i] == 'D':\n",
    "                cnts[i + 1] -= 1\n",
    "                if cnts[i + 1] == 0: stack.append(i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        nums = [i for i in range(0,len(s)+1)]\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            if c == \"I\":\n",
    "                ans.append(nums.pop(0))\n",
    "            else:\n",
    "                ans.append(nums.pop(-1))\n",
    "        ans.append(nums.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        tmp = list(range(n+1))\n",
    "        l, r = 0, n\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            if s[i] == \"I\":\n",
    "                ret.append(tmp[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                ret.append(tmp[r])\n",
    "                r -= 1\n",
    "        return ret+[tmp[r]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        que_n = deque()\n",
    "        ans = []\n",
    "        for i in range(n + 1):\n",
    "            que_n.append(i)\n",
    "        for j in range(n):\n",
    "            if s[j] == 'I':\n",
    "                ans.append(que_n.popleft())\n",
    "            else:\n",
    "                ans.append(que_n.pop())\n",
    "        ans.append(que_n.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n=len(s)+1\n",
    "        list_1=[0]*(n)\n",
    "        list_2=[0]*(n)\n",
    "        for i in range(n):\n",
    "            list_1[i]=i\n",
    "        for j in range(n-1):\n",
    "            if s[j] =='I':\n",
    "                list_2[j]=list_1[0]\n",
    "                del list_1[0]\n",
    "            else:\n",
    "                list_2[j]=list_1[-1]\n",
    "                del list_1[-1]\n",
    "            list_2[-1]=list_1[0]\n",
    "        return list_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans=[]\n",
    "        nums=list(range(len(s)+1))\n",
    "        l,r=0,len(s)\n",
    "        for i in s:\n",
    "            if i=='I':\n",
    "                ans.append(nums[l])\n",
    "                l+=1\n",
    "            else:\n",
    "                ans.append(nums[r])\n",
    "                r-=1\n",
    "        ans.append(nums[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        l=len(s)+1\n",
    "        t=list(range(0,l))\n",
    "        res=[]\n",
    "        for i in s:\n",
    "            if i==\"I\":\n",
    "                res.append(t.pop(0))\n",
    "            else:\n",
    "                res.append(t.pop(-1))\n",
    "        res.append(t[0])\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "\n",
    "        n = len(s)\n",
    "        nums = [0 for _ in range(n+1)]\n",
    "\n",
    "        i,up,low = 0,0,0\n",
    "        while i < n:\n",
    "            \n",
    "            if s[i] == 'I':\n",
    "                up += 1\n",
    "                nums[i+1] = up\n",
    "            \n",
    "            else:\n",
    "                low -= 1\n",
    "                nums[i+1] = low\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return [num + abs(low) for num in nums]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        nums = [i for i in range(len(s)+1)]\n",
    "        nums_que = deque(nums)\n",
    "        res = []\n",
    "        for item in s:\n",
    "            if item == \"I\":\n",
    "                res.append(nums_que.popleft())\n",
    "            else:\n",
    "                res.append(nums_que.pop())\n",
    "        res.append(nums_que.popleft())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans=[]\n",
    "        q=list(range(0,len(s)+1))\n",
    "        for i in s:\n",
    "            if i=='I':\n",
    "                ans.append(min(q))\n",
    "                q.remove(min(q))\n",
    "            else:\n",
    "                ans.append(max(q))\n",
    "                q.remove(max(q))\n",
    "        ans.append(max(q))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        start, end = 0, len(s)\n",
    "        res = []\n",
    "        for c in s:\n",
    "            if c == 'I':\n",
    "                res.append(start)\n",
    "                start += 1\n",
    "            else:\n",
    "                res.append(end)\n",
    "                end -= 1\n",
    "        res.append((set(range(len(s)+1)) - set(res)).pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        inDegree = [0] * (len(s) + 1)\n",
    "        edge = [list() for _ in range(len(s) + 1)]\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'I':\n",
    "                inDegree[i] += 1\n",
    "                edge[i + 1].append(i)\n",
    "            else:\n",
    "                inDegree[i + 1] += 1\n",
    "                edge[i].append(i + 1)\n",
    "\n",
    "        stk = list()\n",
    "        for i in range(len(s) + 1):\n",
    "            if inDegree[i] == 0:\n",
    "                stk.append(i)\n",
    "\n",
    "        ans = [0] * (len(s) + 1)\n",
    "        cnt = len(s)\n",
    "        while stk:\n",
    "            cur = stk.pop()\n",
    "            ans[cur] = cnt\n",
    "            cnt -= 1\n",
    "            for adj in edge[cur]:\n",
    "                inDegree[adj] -= 1\n",
    "                if inDegree[adj] == 0:\n",
    "                    stk.append(adj)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        out = [0] * (n+1)\n",
    "        st = [0]\n",
    "        for c in s:\n",
    "            if c == \"I\":\n",
    "                st.append(st[-1]+1)\n",
    "            else:\n",
    "                st.append(st[-1]-1)\n",
    "        temp = sorted((st[i],i) for i in range(n+1))\n",
    "        for j,p in enumerate(temp):\n",
    "            pi = p[1]\n",
    "            out[pi] = j\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "\n",
    "        n = len(s)\n",
    "        nums = [0 for _ in range(n+1)]\n",
    "\n",
    "        i,up,low = 0,0,0\n",
    "        while i < n:\n",
    "            \n",
    "            if s[i] == 'I':\n",
    "                up += 1\n",
    "                nums[i+1] = up\n",
    "            \n",
    "            else:\n",
    "                low -= 1\n",
    "                nums[i+1] = low\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return [num - low for num in nums]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ret=[0]\n",
    "        max,min=0,0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='I':\n",
    "                max+=1\n",
    "                ret.append(max)\n",
    "            else:\n",
    "                min-=1\n",
    "                ret.append(min)\n",
    "        #f=min(ret)\n",
    "        \n",
    "        return [a-min for a in ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def diStringMatch(self, s):\n",
    "        n=len(s)\n",
    "        li=list(range(n+1))\n",
    "        left,right=0,n\n",
    "        res=[]\n",
    "        if s[0]=='I':\n",
    "            res.append(li[left])\n",
    "            left+=1\n",
    "        else:\n",
    "            res.append(li[right])\n",
    "            right-=1\n",
    "        for i in range(1,len(s)):\n",
    "            c=s[i]\n",
    "            if c=='I':\n",
    "                res.append(li[left])\n",
    "                left+=1\n",
    "            else:\n",
    "                res.append(li[right])\n",
    "                right-=1\n",
    "        while left<=right:\n",
    "            res.append(left)\n",
    "            left+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        arr = [i for i in range(len(s) + 1)]\n",
    "        copy = []\n",
    "        max_num = max(arr)\n",
    "        min_num = min(arr)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'I':\n",
    "                copy.append(min_num)\n",
    "                min_num += 1\n",
    "            else:\n",
    "                copy.append(max_num)\n",
    "                max_num -= 1\n",
    "        copy.append(max_num)\n",
    "        return copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        min1=0\n",
    "        max1=0\n",
    "        ans=[0]\n",
    "        for c in s:\n",
    "            if c=='I':\n",
    "                ans.append(max1+1)\n",
    "                max1+=1\n",
    "            else:\n",
    "                ans.append(min1-1)\n",
    "                min1-=1\n",
    "        if min(ans)<0:\n",
    "            ans = [i -min(ans) for i in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        minimum, maximum = 0, len(s)\n",
    "        lst = []\n",
    "        for item in s:\n",
    "            if item == \"I\":\n",
    "                lst.append(minimum)\n",
    "                minimum += 1\n",
    "            else:\n",
    "                lst.append(maximum)\n",
    "                maximum -= 1\n",
    "        lst.extend(list(set(i for i in range(0, len(s) + 1)) - set(lst)))\n",
    "        return lst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        min1=0\n",
    "        max1=0\n",
    "        ans=[0]\n",
    "        for c in s:\n",
    "            if c=='I':\n",
    "                ans.append(max1+1)\n",
    "                max1+=1\n",
    "            else:\n",
    "                ans.append(min1-1)\n",
    "                min1-=1\n",
    "        if min(ans)<0:\n",
    "            ans = [i -min1 for i in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diStringMatch(self, s: str) -> List[int]:\n",
    "        ans = [0] \n",
    "        l, r = -1, 1 \n",
    "        for c in s:\n",
    "            if c == \"I\":\n",
    "                ans.append(r)\n",
    "                r += 1\n",
    "            else:\n",
    "                ans.append(l)\n",
    "                l -= 1\n",
    "        \n",
    "        return [v - l - 1 for v in ans] if l + 1 < 0 else ans \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
